// https://www.lintcode.com/problem/3sum-closest/

public class Solution {
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    public int threeSumClosest(int[] numbers, int target) {
        // write your code here
        int ret = -1;
        int min_diff = Integer.MAX_VALUE;
        Arrays.sort(numbers);
        for (int i = 0; i < (numbers.length - 2); ++i) {
            int start = i + 1, end = numbers.length - 1;
            while (start < end) {
                int tsum = numbers[i] + numbers[start] + numbers[end];
                int diff = Math.abs(tsum - target);
                if (diff == 0) {
                    return target;
                }
                if (diff < min_diff) {
                    min_diff = diff;
                    ret = tsum;
                }
                if (tsum < target) {
                    ++start;
                } else {
                    --end;
                }
            }
        }
        return ret;
    }
}